/**
//有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 
//
// 
// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 
//和 "192.168@1.1" 是 无效 IP 地址。 
// 
//
// 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新
//排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "25525511135"
//输出：["255.255.11.135","255.255.111.35"]
// 
//
// 示例 2： 
//
// 
//输入：s = "0000"
//输出：["0.0.0.0"]
// 
//
// 示例 3： 
//
// 
//输入：s = "101023"
//输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 20 
// s 仅由数字组成 
// 
// Related Topics 字符串 回溯 👍 887 👎 0

*/

package com.xixi.basicAlgroithms.backtracking;

import java.util.ArrayList;
import java.util.List;

public class ID00093RestoreIpAddresses {
public static void main(String[] args) {

    Solution solution = new ID00093RestoreIpAddresses().new Solution();
    System.out.println(solution.restoreIpAddresses("172162541"));
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //快照集合
    public List<String> result = new ArrayList<>();


    public List<String> restoreIpAddresses(String s) {

        backTracking(s.toCharArray(), 0, s.length() + 3, 0, new char[s.length() + 3], new ArrayList<>(), 0);

        return result;

    }


    public void backTracking(char[] sChar, int sIndex, int resultLength, int resultIndex, char[] path, List<Character> nowBlock, int blockNum){

        if(sChar.length > 12){
            return;
        }

        if(sIndex == sChar.length ){
            if(resultIndex == resultLength){
                String snap = new String(path);
                result.add(snap); //照快照
            }

            return;
        }







        char nowChar = sChar[sIndex];





        //nowBlock位数小于3
        if( nowBlock.size() < 3){

            if(!(nowBlock.size() == 1 && nowBlock.get(0) == '0')){ //前面的block不是前导0

                //不切割,nowBlock和当前字符合体成一个block,block中第一个是非前导0，且
                nowBlock.add(nowChar); //当前block添加

                if(nowBlock.size() == 3){ //需要判断是否小于255
                    StringBuilder sb = new StringBuilder();
                    for (Character c : nowBlock){
                        sb.append(c);
                    }
                    int nowBlockValue = Integer.parseInt(sb.toString());
                    if(nowBlockValue <= 255){
                        path[resultIndex] = nowChar; //赋值
                        backTracking(sChar,sIndex + 1, resultLength, resultIndex + 1, path, nowBlock, blockNum);
                        //去除选择
                        path[resultIndex] = '*';
                    }
                }else{
                    path[resultIndex] = nowChar; //赋值
                    backTracking(sChar,sIndex + 1, resultLength, resultIndex + 1, path, nowBlock, blockNum);
                    //去除选择
                    path[resultIndex] = '*';
                }



                nowBlock.remove(nowBlock.size() -1);
            }



        }
        //nowBlock位数等于3
            //割
            //resultIndex != 0 不能和前面分割
            //后面的数字个数 sChar - sIndex 大于等于12-sIndex
            //割的时候要新生成nowBlock
            //恢复的时候要去掉点.

        if(resultIndex !=0 && blockNum < 3){
            path[resultIndex] = '.'; //和前面割了
            resultIndex++;
            path[resultIndex] = nowChar;
            List<Character> newBlockList = new ArrayList<Character>();//不要破坏当前的nowBlock指针
            newBlockList.add(nowChar);

            backTracking(sChar,sIndex + 1, resultLength, resultIndex + 1, path, newBlockList,blockNum + 1);

            path[resultIndex] = '*';
            resultIndex--;
            path[resultIndex] = '*'; //别忘去掉点


        }







    }



}
//leetcode submit region end(Prohibit modification and deletion)




}